/*
题目: 子数组最小乘积的最大值
一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

    比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对  109 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

https://leetcode.cn/problems/maximum-subarray-min-product
 */
public class MaxSumMinProduct {
    public int maxSumMinProduct(int[] nums) {
        int n = nums.length;
        // 找出最小乘积的最大值
        // 最小乘积 = 数组和 * 最小值, 要让最小乘积最大
        // 求出以 每一个元素为最小值 的子数组, 再乘上这个数组和

        // 前缀和 -> 便于求出子数组和
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i ++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        // 以这个元素为最小值, 并且是最左边的元素 的子数组 的长度
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<Integer> stk = new Stack<> ();

        // 单调栈
        for (int i = 0; i < n; i ++) {
            while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
                stk.pop();
            }
            // 以这个元素为 最右边元素, 并且是最小值的 子数组长度
            right[i] = i - (stk.isEmpty() ? -1 : stk.peek());
            stk.push(i);
        }

        stk.clear();
        for (int i = n - 1; i >= 0; i --) {
            while (!stk.isEmpty() && nums[stk.peek()] >= nums[i]) {
                stk.pop();
            }
            left[i] = (stk.isEmpty() ? n : stk.peek()) - i;
            stk.push(i);
        }

        long src = 0;
        final int MOD = (int) 1e9 + 7;
        for (int i = 0; i < n; i ++) {
            long result = (prefix[i + left[i]] - prefix[i - right[i] + 1]) * nums[i];
            src = Math.max(src, result);
        }
        return (int) (src % MOD);
    }
}
